
#include "Common.h"

using namespace ttg::math;
using namespace ttg::threads;

//-----------------------
//--- PrimeFinderPool ---
//-----------------------

PrimeFinder *PrimeFinderPool::acquireFinder()
{
	bool *buffer = NULL;
	//Trying to get existen buffer.
	locker.enter();
	if (!buffers.empty())
	{
		buffer = buffers[buffers.size() - 1];
		buffers.pop_back();
	}
	locker.leave();
	//Or creating a new one.
	if (buffer == NULL)
		buffer = new bool[buffer_size];
	return new PrimeFinder(buffer, buffer_size);
}

void PrimeFinderPool::releaseFinder(PrimeFinder *&finder)
{
	locker.enter();
	buffers.push_back(finder->buffer);
	locker.leave();
	SAFE_DELETE(finder);
}

uint64 PrimeFinderPool::findPrimes(uint64 lo, uint64 hi)
{
	PrimeFinder *finder = acquireFinder();
	uint64 res = finder->findPrimes(lo, hi);
	releaseFinder(finder);
	return res;
}

PrimeFinderPool::~PrimeFinderPool()
{
	locker.enter();
	for (size_t i = 0; i < buffers.size(); i++)
		SAFE_DELETE(buffers[i]);
	buffers.clear();
	locker.leave();
}

//-------------------
//--- PrimeFinder ---
//-------------------

size_t PrimeFinder::clearBuffer(size_t range_length)
{
	size_t res = 0;
	buffer[0] = false;
	//Clearing and counting.
	for (size_t i = 1; i < range_length; i++)
	{
		res += (buffer[i] ? 1 : 0);
		buffer[i] = true;
	}
	//Clearing only.
	for (size_t i = range_length; i < buffer_size; i++)
		buffer[i] = true;
	return res;
}

void PrimeFinder::strikeNumber(size_t number, uint64 range_start, size_t range_length)
{
	//Aligning.
	size_t i = number - (size_t)(range_start % number);
	if (number >= range_start)
		i += number;
	//Striking.
	while (i < range_length)
	{
		buffer[i] = false;
		i += number;
	}
}

size_t PrimeFinder::findPrimesUsingBuffer(uint64 range_start, size_t range_length)
{
	//Finding bound for strikers.
	size_t bound = (size_t)(sqrt((long double)range_start + range_length)) + 1;
	//Striking.
	strikeNumber(2, range_start, range_length);
	strikeNumber(3, range_start, range_length);
	size_t i = 5;
	while (i <= bound)
	{
		strikeNumber(i, range_start, range_length);
		strikeNumber(i + 2, range_start, range_length);
		i += 6;
	}
	//Clearing buffer and returning count of prime numbers.
	return clearBuffer(range_length);
}

uint64 PrimeFinder::findPrimes(uint64 lo, uint64 hi)
{
	uint64 range_length = hi - lo;
	uint64 tile_count = range_length / buffer_size;
	uint64 res = 0;
	//Counting primes for full tiles.
	for (size_t i = 0; i < tile_count; i++)
		res += findPrimesUsingBuffer(lo + i * buffer_size, buffer_size);
	//Counting primes for the last tile.
	if (range_length % buffer_size != 0)
		res += findPrimesUsingBuffer(lo + tile_count * buffer_size,
									 (size_t)(range_length % buffer_size));
	//Returning result.
	return res;
}
